package leedcode_path.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.IllegalFormatFlagsException;
import java.util.List;

public class 子集2 {
    /*
    * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]*/

    List<Integer> path=new ArrayList<Integer>();
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] used=new boolean[nums.length];
        Arrays.fill(used,false);
        backtracking(nums,0,used);
        return res;
    }
    public void backtracking(int[] num,int startindex,boolean[] used){
        res.add(new ArrayList<>(path));
        if (startindex==num.length){
            return;
        }
        for (int i = startindex; i <num.length ; i++) {
            if (i>0&&num[i]==num[i-1]&&used[i-1]==false){
                continue;
            }
            path.add(num[i]);
            used[i]=true;
            backtracking(num, i + 1, used);
            used[i]=false;
            path.remove(path.size()-1);
        }

    }
}
